package main

import (
	"fmt"
	"time"
)

func main() {
	start := time.Now()
	for i := 0; i <= 25; i++ {
		fmt.Printf("fibonacci(%d) is: %d\n", i, fibonacci(i))
	}
	end := time.Now()
	delta := end.Sub(start)
	fmt.Printf("longCalculation took this amount of time: %s\n", delta)
}

// 斐波那契数列
/*
递归实现每次计算斐波那契数时都会重复计算已经计算过的子问题。这种重复计算导致时间复杂度为 O(2^n)，非常低效，尤其对于较大的 n。

举个例子，计算 fibonacci(5) 会递归地计算 fibonacci(4) 和 fibonacci(3)，而在计算 fibonacci(4) 时，又会重复计算 fibonacci(3) 和 fibonacci(2)，这些子问题会被重复多次计算。
*/
func fibonacci(n int) int {
	if n <= 1 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}
